package leetcode;

import java.util.LinkedList;
import java.util.List;

/**
 * Created by Ghost on 2014/11/18 0018.
 */
public class Gray_Code {
    private List<String> rst = new LinkedList<String>();

    private void yarg(String prefix, int n) {
        if (n == 0)
            rst.add(prefix);
        else {
            gray(prefix + "1", n - 1);
            yarg(prefix + "0", n - 1);
        }
    }

    private void gray(String prefix, int n) {
        if (n == 0)
            rst.add(prefix);
        else {
            gray(prefix + "0", n - 1);
            yarg(prefix + "1", n - 1);
        }
    }

    private int toInt(String str) {
        char[] chars = str.toCharArray();
        int p = chars.length - 1;
        int rst = 0;
        for (char aChar : chars) {
            rst += Integer.parseInt("" + aChar) * Math.pow(2, p);
            p--;
        }
        return rst;
    }

    public List<Integer> grayCode(int n) {
        gray("", n);
        List<Integer> rst2 = new LinkedList<Integer>();
        for (String str : rst) {
            int num = toInt(str);
            rst2.add(num);
        }
        return rst2;
    }

    public static void main(String[] args){
        Gray_Code gray_code = new Gray_Code();
        int n = 5;
        System.out.println(gray_code.grayCode(n));
    }
}
